class Solution {
public:
    bool vis[400][400];
    int rex[4]={0,0,1,-1};
    int rey[4]={1,-1,0,0};
    void dfs(int x,int y,int mx,int my,vector<vector<char>>& grid)
    {
        vis[x][y]=true;
        for(int i=0;i<4;i++){
            int x1=x+rex[i];
            int y1=y+rey[i];
            if(x1>=0&&x1<mx&&y1>=0&&y1<my&&grid[x1][y1]=='1'&&!vis[x1][y1]){
                dfs(x1,y1,mx,my,grid);
            }
        }
    }
    int numIslands(vector<vector<char>>& grid) {
        memset(vis,false,sizeof(vis));
        int mx=grid.size();
        int my=grid[0].size();
        int ans=0;
        for(int i=0;i<mx;i++)
        {
            for(int j=0;j<my;j++)
            {
                if(grid[i][j]=='1'&&!vis[i][j]){
                    dfs(i,j,mx,my,grid);
                    ans++;
                }
            }
        }
        return ans;
    }
};